package com.caochenlei.graph;

import java.util.LinkedList;
import java.util.Queue;

public class Digraph {
    private int N;                      //表示顶点数目
    private int E;                      //表示边的数目
    private Queue<Integer>[] adj;       //表示邻接表

    public Digraph(int n) {
        this.N = n;                     //初始化顶点数目
        this.E = 0;                     //初始化边的数目
        this.adj = new LinkedList[n];   //初始化邻接表

        for (int i = 0; i < adj.length; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    //获取顶点数目
    public int size() {
        return N;
    }

    //获取边的数目
    public int edge() {
        return E;
    }

    //添加一条边
    public void addEdge(int v, int w) {
        adj[v].add(w);                  //在v的链表中添加w
        E++;                            //图的边数加一
    }

    //删除一条边
    public void removeEdge(int v, int w) {
        adj[v].remove(w);               //在v的链表中删除w
        E--;                            //图的边数减一
    }

    //获取v的邻点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    //获取反向图
    public Digraph reverse() {
        Digraph r = new Digraph(N);
        for (int v = 0; v < N; v++) {
            for (Integer w : adj[v]) {
                r.addEdge(w, v);
            }
        }
        return r;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(N + " vertices, ");
        sb.append(E + " edges\n");
        for (int v = 0; v < N; v++) {
            sb.append(v + ": ");
            for (Integer w : adj(v)) {
                sb.append(w + " ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}
